/**
 * StereoHippieClass.java
 * Purpose: My Class.
 *
 * @author Hippie.Stereo - hippie.stereo@gmail.com
 * @author João Luís Palma Cardeira
 * @version 1.0 20/05/2013
 */

class HeapSortCLS
{
	int intHeapSize = 0;
	//HeapSort_EDA this;
	int ListaDados[];

	protected HeapSortCLS(int[] listaIn)
	{
		ListaDados = listaIn;
		intHeapSize = ListaDados.length;
	}

	protected void _Sort()
	{
		_BuildMaxHeap();
		
		for(int IncCount = ListaDados.length - 1; IncCount >= 0; IncCount--)
		{
			int temp = ListaDados[0];
			ListaDados[0] = ListaDados[IncCount];
			ListaDados[IncCount] = temp;
			_setHeapSize(_getHeapSize() - 1);
			_MaxHeapify(0);
		}
	}

	protected void _MaxHeapify(int intIn)
	{	
		int l = _leftNode(intIn);
		int r = _rightNode(intIn);
		int largest;
		
		if(l <= _getHeapSize() && ListaDados[l] > ListaDados[intIn])
		{largest = l;}
		else
		{largest = intIn;}
		
		if(r <= _getHeapSize() && ListaDados[r] > ListaDados[largest])
		{largest = r;}
		
		if(largest != intIn)
		{
			int temp = ListaDados[intIn];
			ListaDados[intIn] = ListaDados[largest];
			ListaDados[largest] = temp;
			_MaxHeapify(largest);
		}
	}
	
	protected void _BuildMaxHeap()
	{	
		_setHeapSize(ListaDados.length - 1);
		
		for(int IncCount = ((ListaDados.length - 1)/2); IncCount >= 0; IncCount--)
		{
			_MaxHeapify(IncCount);
		}
	}
	
	protected int HeapMaximum()
	{
		return ListaDados[1];
	}

	protected int ReturnExtractMax()
	{
		int max = 0;

		if(_getHeapSize() < 1)
		{
			System.out.println("\n\nHEAP UNDERFLOW\n\n");
		}

		max = ListaDados[1];
		ListaDados[1] = ListaDados[_getHeapSize()];
		_setHeapSize(_getHeapSize() - 1);
		_MaxHeapify(1);

		return max;
	}	

	protected void HeapIncreaseKey(int i, int key)
	{
		if (key < ListaDados[i])
		{
			System.out.println("\n\nNEW KEY IS SMALLER\n\n");
		}

		ListaDados[i] = key;

		while (i > 1 && ListaDados[_parentNode(i)] < ListaDados[i])
		{
			int temp = ListaDados[i];
			ListaDados[i] = ListaDados[_parentNode(i)];
			ListaDados[_parentNode(i)] = temp;
			i = _parentNode(i);
		}
	}

	protected void MaxHeapInsert(int key)
	{
		_setHeapSize(_getHeapSize() + 1);
		ListaDados[_getHeapSize()] = -99999;
		HeapIncreaseKey(_getHeapSize(), key);
	}

	protected int _parentNode(int intIn)
	{
		return (intIn/2) + 1;
	}

	protected int _leftNode(int intIn)
	{
		return (intIn*2) + 1;
	}

	protected int _rightNode(int intIn)
	{
		return (intIn*2) + 2;
	}
	
	protected void _setHeapSize(int intIn)
	{
		intHeapSize = intIn;
	}

	protected int _getHeapSize()
	{
		return intHeapSize;
	}	
}